﻿\subsection{Языки нижнего уровня и кодировка Пансьё}
\label{subsection:bigexp-intro}

Если $\Sigma$~--- алфавит, $|\Sigma| = k$, то, согласно \cite{Dejean}, $RT(4) = 7/5$ и
$RT(k) = k/(k{-}1)$ для $k \ge 5$. Число $RT(k)$ называется \textit{границей повторяемости}
и означает, что $\beta$-свободный язык над алфавитом из $k$ букв является конечным, если
$\beta \le RT(k)$, и бесконечным в противном случае. В работе мы рассматриваем
$\beta$-свободные языки, для которых $RT(k) < \beta \le (k{-}1)/(k{-}2)$, или
\textit{языки первого уровня}.

Заметим, что если слово $w\in\Sigma^*$ лежит в языке первого уровня, то любое подслово $w$
длины $(k{-}1)$ (в том числе, префикс) состоит из различных букв. Это значит, что мы можем
закодировать $w = w[1..n]$ ($n \ge k$) бинарным словом $P(w) \in \{0,1\}^{n-k+1}$ по
следующему правилу:
$$
P(w)[i] = 
\begin{cases}
  0, & w[i+k-1] = w[i], \\
  1, & w[i+k-1] \notin \{w[i], \ldots, w[i+k-2]\}.\\
\end{cases}
$$
Например, при $\Sigma=\{1,\ldots,6\}$ слово $w = 12345163241$ будет закодировано как $P(w) = 010110$.
$P(w)$ называется \textit{кодом Пансьё} слова $w$.
\begin{rmrk} \label{pansiot-rmrk}
По коду Пансьё $P(w)$ мы можем восстановить $w$ с точностью до перестановки букв алфавита.
Таким образом, коды Пансьё однозначно соответствуют классам эквивалентных слов.
\end{rmrk}
Пусть $P^{-1}(w)$~--- лексикографически минимальный из всех возможных прообразов $w$.

\begin{lmm} \label{pansiot}
Пусть $L\in\Sigma^{*}$~--- язык первого уровня.
\item[(1)] Пусть $w \in \Sigma^*$, $z$~--- подслово $P(w)$, $P^{-1}(z) \notin L$.
Тогда $w \notin L$.
\item[(2)] Если $w \in L$, то в $P(w)$ нет подслов $00$ и $111$.
\end{lmm}
\begin{proof}
(1) Существует такая перестановка букв алфавита, что образ $P^{-1}(z)$ будет являться
подсловом $w$ и не будет лежать в $L$. Значит, $w \notin L$, так как язык $L$ факториальный.

(2) Пусть $|\Sigma|=k$. Несложно проверить, что $P^{-1}(00)$ имеет экспоненту $\frac{k+1}{k-1}$,
а слово $P^{-1}(111)$ имеет экспоненту $\frac{k+2}{k}$. Слова с такими экспонентами запрещены
в языках первого уровня.
\end{proof}

Из леммы~\ref{pansiot} следует, что мы можем вместо языка над $\Sigma$ с конечным
антисловарём $M$, рассматривать язык над $\{0,1\}$ с конечным антисловарём кодов
Пансьё всех слов из $M$. Их индексы роста будут совпадать.

Итак, для языков нижнего уровня мы можем построить коды Пансьё всех слов
антисловаря,
после чего считать индекс роста языка над бинарным алфавитом.
Ввиду замечания~\ref{pansiot-rmrk}, автомат, построенный по антисловарю,
составленному из кодов Пансьё, и автомат, построенный по антисловарю представителей,
имеют одинаковое с точностью до $O(|\Sigma|)$ число вершин. Поскольку автомат с $n$ состояниями над
$k$-буквенным алфавитом задаётся таблицей размером $n \times k$, переход к кодам
Пансьё уменьшает объём памяти, необходимой для хранения автомата, в $|\Sigma|/2$ раз.
